home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / BARNET / COMPILER / SATHER / !Sather / Library / Graphs / Graphs.sam next >
Text File  |  1997-03-09  |  7KB  |  245 lines
  1. (* 
  2.  
  3. These classes are the result of many discussions among David
  4. Stoutamire, Jerry Feldman, Wolf Zimmerman and myself (Ben Gomes).
  5. They borrow many ideas from Karla and LEDA. A couple of the
  6. algorithms (bellman_ford and dijkstra) were translated from LEDA.
  7.  
  8.  
  9. Constructing a graph:
  10.    g: DIGRAPH := #;
  11.    n1 ::= g.add_node; n2 ::= g.add_node; n3 ::= g.add_node;
  12.    g.connect(n1,n2).connect(n1,n3);
  13.  
  14. This constructs:
  15.        1
  16.       /\
  17.      2  3
  18.  
  19. Getting the nodes in depth first order:
  20.     l:LIST{INT} := #;
  21.     loop n: INT := DIGRAPH_ALG::dfs!(g);
  22.          l := l.append(n);
  23.      end;
  24. Getting the layers of the graph:
  25.     l: LIST{SET{INT}} := #;
  26.     loop s: SET{INT} := DIGRAPH_ALG::layer!(g);
  27.          l := l.append(s);
  28.     end;
  29.  
  30.  
  31. Graph Views
  32. -----------
  33. Views of the nodes of a graph:
  34.    g1: DIGRAPH{INT} := #;
  35.    g1n1 ::= g1.add_node(1); g1n2 ::= g.add_node(2); g1n4 ::= g.add_node(4);
  36. Which constructs:
  37.    1
  38.    |
  39.    2  4 
  40.    g2: DIGRAPH{INT} := #;
  41.    g2n1 ::= g1.add_node(1); g2n2 ::= g.add_node(2); g2n5 ::= g.add_node(5);
  42. Which constructs:
  43.    1
  44.    |
  45.    2  5 
  46.  
  47. We can now find the intesection of nodes in the two graphs by looking
  48. at the edge view and then finding the intersection
  49.   node_view1:DIGRAPH_NODE_SET_VIEW{INT,DIGRAPH{INT}} := #(g1);
  50.   node_view2:DIGRAPH_NODE_SET_VIEW{INT,DIGRAPH{INT}} := #(g2);
  51. Finding the union of the nodes in two graphs:
  52.    u: $RO_SET{INT} := node_view1.union(node_view2); = {1,2,4,5}
  53. Finding the difference between the sets of nodes in two graphs:
  54.    u: $RO_SET{INT} := node_view1.diff(node_view2);   = {4,5}
  55.  
  56. Views of the edges of a graph:
  57. The following graph is used in several of the following examples
  58.    graph_n3_n4_n1: DIGRAPH{INT} := #;
  59.    n3 ::= g.add_node(3); 
  60.    n4 ::= g.add_node(4); 
  61.    n1 ::= g.add_node(1)
  62. graph_n3_n4_n1 is n3->n4<-n1
  63.  
  64. es: DIGRAPH_EDGE_SET_VIEW{INT,DIGRAPH{INT}} := #(graph_n3_n4_n1);
  65.  
  66. Th set of edge, 'es' is {#DIEDGE{INT}(3,4) #DIEDGE{INT}(1,4) }
  67.  
  68. There are also views of the incoming and outgoing nodes of a particular
  69. node in the graph i.e. views of neighbors of a node:
  70.    inc: DIGRAPH_INC_SET_VIEW{INT,DIGRAPH{INT}} := #(graph_n3_n4_n1,n4);
  71.  
  72. The set 'inc' consists of all the incoming nodes into the node 'n4',
  73. which consists of the nodes {3,1}. This set may be used to determine
  74. whether two different nodes  have any common incoming edges
  75.  
  76.   outg: DIGRAPH_OUTG_SET_VIEW{INT,DIGRAPH{INT}} := #(graph_n3_n4_n1,n3);
  77. The set 'outg' consists of all the outgoing nodes from the node 'n3'
  78. which consists  of the element n4 i.e. 4
  79.  
  80.  
  81. View of the nodes as a reversed graph:
  82.    rg ::= #DIGRAPH_REV_DIGRAPH_VIEW{INT}(graph_n3_n4_n1);
  83. rg is then the graph  3 <- 4-> 1  
  84. Thus, we would have the following
  85.   #OUT+rg.has_edge(#DIEDGE{INT}(4,3)); -- Prints true
  86.   #OUT+rg.has_edge(#DIEDGE{INT}(3,4)); -- Prints false
  87.  
  88. A View of a graph filtered through a node predicate:
  89.  
  90.   g ::= #DIGRAPH{INT};
  91.   n1 ::= g.add_node(1); n2 ::= g.add_node(2); n3 ::= g.add_node(3); 
  92.   n4 ::= g.add_node(4); n5 ::= g.add_node(5); n0 ::= g.add_node(0); 
  93.   g.connect(n3,0);  g.connect(n1,n2); g.connect(n2,n4);
  94.   g.connect(n2,n5); g.connect(n1,n3);
  95.        1
  96.       /\
  97.      2   3
  98.    /  \   \
  99.   4    5   0
  100.  
  101. Now consider the following node filter routine, which only permits
  102. nodes which are less than 4
  103.  
  104.   node_rout:ROUT{INT}:BOOL := bind(_:INT.is_lt(4));
  105.   fv:FILTERGRAPH_DIGRAPH_VIEW{INT,DIGRAPH{INT}} := #(g,node_rout);
  106.  
  107. fv is now of the form
  108.        1
  109.       /\
  110.      2   3
  111.           \
  112.            0
  113.  
  114.  
  115. A Few Algorithms on Weighted Graphs
  116. -----------------------------------
  117. Bellman Ford for shortest paths and predecessors in
  118. the shortest path tree:
  119.    g: WTD_DIGRAPH{INT,FLT} := #; 
  120.       -- A weighted graph with nodes of type
  121.       -- INT and node and edge weights of type FLT
  122.    n1: INT := g.add_node(1);
  123.    n2: INT := g.add_node(2);
  124.    n3: INT := g.add_node(3);
  125.    n4: INT := g.add_node(4);
  126.    g.connect(n1,n2,10.0); g.connect(n1,n3,11.0); 
  127.    etc. until we have
  128.          *1*
  129.     10.0/ | \ 11.0
  130.        / 1.0 \
  131.      *2*  |  *3*
  132.   13.0 \  |  / 11.0
  133.         \ | /
  134.          *4*
  135.    distances: MAP{INT,FLT}; 
  136.    preds: MAP{INT,INT};     -- Predecessor mapping
  137.    res::=g.bellman_ford(n1,out distances, out preds);
  138.   
  139. Distances maps nodes (of type INT) to the FLT distance from the source
  140. node (the node n1 is supplied is supplied as the source).  Thus,
  141. node[4] is at distance 1.0 via the edge (1,4) preds maps nodes to
  142. their predecessor in the shortest path tree And the precedessor of
  143. node[4] in the shortest path tree is 1.  The full mappings returned
  144. are:
  145.    distances[4] = 1.0 [3] = 11.0 [2] = 10.0 
  146.    preds[4] = 1 [3] = 1 [2] = 1
  147.   
  148. Dijkstra algorithm for single source shortest paths if the
  149. graph has non-negative weights. Very similar, but more
  150. efficient than bellman ford, if the graph has no negative
  151. weights
  152.  
  153. max_weight_path_node! Yields successive nodes along the maximum weight
  154. path in the graph. Using the same graph as before:
  155.   res: A_LIST{INT} := #;
  156.   loop res.append(g.max_weight_path_node!(g,n1,n4)); end;
  157. n1 is specified as the source node and n4 is specified as the sink
  158. node. The result, which is stored as elements of the list "res" will
  159. simply consist of n1,n2,n4, whose path has a weight of 23
  160.  
  161.  
  162.  
  163. *)
  164.  
  165. -- Abstract and concrete edges
  166. edges.sa  -has edges.sa 
  167.         $EDGE 
  168.         UEDGE 
  169.         DIEDGE
  170.  
  171. -- Abstraction over all graphs, parametrized over node and edge types
  172. abs_graph.sa  -has abs_graph.sa
  173.         $GRAPH
  174.  
  175. -- Graph exceptions
  176. graph_exc.sa -has graph_exc.sa
  177.         GRAPH_EXC
  178.     
  179. -- Abstract digraphs
  180. a_digraph.sa -has a_digraph.sa 
  181.         $RO_DIGRAPH 
  182.         $DIGRAPH
  183.  
  184. -- Digraphs
  185. digrph_inc.sa  -has digrph_inc.sa
  186.         RO_DIGRAPH_INCL 
  187.         DIGRAPH_INCL 
  188.  
  189. -- Various views of a digraph
  190. digrph_vws.sa -has digrph_vws.sa
  191.         DIGRAPH_NODE_SET_VIEW  
  192.         DIGRAPH_EDGE_SET_VIEW
  193.         DIGRAPH_INC_SET_VIEW 
  194.         DIGRAPH_OUTG_SET_VIEW
  195.         DIGRAPH_REV_DIGRAPH_VIEW 
  196.         FILTERGRAPH_DIGRAPH_VIEW 
  197.  
  198. digraph.sa  -has digraph.sa
  199.         DIGRAPH
  200.  
  201. digrph_alg.sa    -has digrph_alg.sa    -- Directed graph algorithms
  202.         DIGRAPH_ALG    
  203.         DIGRAPH_ALG_INCL
  204.  
  205. test/digraph.sa    -has test/digraph.sa
  206.         TEST_DIGRAPH
  207.  
  208.  
  209. test/digr_views.sa -has test/digr_views.sa
  210.         TEST_DIGRAPH_VIEWS
  211.  
  212. -- Undirected graphs
  213. abs_ugraph.sa -has  abs_ugraph.sa
  214.         $RO_UGRAPH
  215.         $UGRAPH
  216.  
  217. ugraph_inc.sa -has ugraph_inc.sa
  218.         UGRAPH_INCL
  219.  
  220.  
  221. ugraph.sa  -has ugraph.sa  -- An undirected digraph implementation
  222.         UGRAPH
  223.  
  224. test/ugraph.sa    -has test/ugraph.sa -- Undirected graph test
  225.          TEST_UGRAPH
  226.  
  227.  
  228. -- labelled digraphs
  229. lbld_digr.sa     -has lbld_digr.sa
  230.           $LBLD_DIGRAPH
  231.            LBLD_DIGRAPH_INCL
  232.            LBLD_DIGRAPH
  233.  
  234. wtd_digr.sa     -has wtd_digr.sa
  235.            WTD_DIGRAPH
  236.  
  237. wtd_dgr_al.sa  -has wtd_dgr_al.sa
  238.          WTD_DIGRAPH_ALG
  239.  
  240. test/wtd_digr.sa  -has test/wtd_digr.sa
  241.         TEST_WTD_DIGRAPH
  242.  
  243. -- Dumping to dot
  244. --graph_to_dot.sa   -has graph_to_dot.sa $SUPPORTS_DOT DIGRAPH_TO_DOT TEST_DIGRAPH_TO_DOT
  245.